package algorithm_primary.studyMySelf.十五threeNumberSum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 衡孟浩
 * @date 2023/8/15 9:36
 * <p>
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
 * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 * <p>
 * 你返回所有和为 0 且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * <p>
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * 解释：
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 * 注意，输出的顺序和三元组的顺序并不重要。
 * 示例 2：
 * <p>
 * 输入：nums = [0,1,1]
 * 输出：[]
 * 解释：唯一可能的三元组和不为 0 。
 * 示例 3：
 * <p>
 * 输入：nums = [0,0,0]
 * 输出：[[0,0,0]]
 * 解释：唯一可能的三元组和为 0 。
 */
public class TestMain {

    public static void main(String[] args) {
        int[] test = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = threeSum(test);
        System.out.println("lists = " + lists);
    }

    public static List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {

            if (nums[i] > 0)break;
            if ((nums[i] + nums[i+1] + nums[i+2]) > 0) break;
            if ((nums[i] + nums[nums.length - 1] + nums[nums.length - 2]) < 0) continue;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int leftIndex = i + 1;
            int rightIndex = nums.length - 1;

            while (leftIndex < rightIndex) {
                int sum = nums[i] + nums[leftIndex] + nums[rightIndex];
                if (sum > 0) {
                    while (leftIndex < rightIndex && nums[rightIndex] == nums[--rightIndex]) ;
                } else if (sum < 0) {
                    while (leftIndex < rightIndex && nums[leftIndex] == nums[++leftIndex]) ;
                } else {
                    List<Integer> list = new ArrayList<>(3);
                    list.add(nums[i]);
                    list.add(nums[leftIndex]);
                    list.add(nums[rightIndex]);
                    res.add(list);
                    while (leftIndex < rightIndex && nums[rightIndex] == nums[--rightIndex]) ;
                    while (leftIndex < rightIndex && nums[leftIndex] == nums[++leftIndex]) ;
                }
            }

        }
        return res;

    }


    /**
     * 官方leetCode
     */
    /*public static List<List<Integer>> threeSum(int[] nums) {
        //数组从小到大排序
        Arrays.sort(nums);
        int len = nums.length;

        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0; i < len -2; i++){
            //如果最小的数大于0则不可能三个数的和为0, 直接退出
            if(nums[i] > 0){
                break;
            }

            //如果和上一个数相同，则有重复解。
            //即当a = d时，a + b + c = d + b + c = 0, 寻找下一个不同的数（简称：去重）
            if(i > 0 && nums[i] == nums[i-1]){    //i > 0是因为可能i = 0时去重出现异常
                continue;
            }

            //取另外两个数，判断三数之和是否为0
            int j = i + 1, k = len - 1;
            int sum;


            while(j < k){
                sum = nums[i] + nums[j] + nums[k];

                //如果三数之和大于0，则说明最大数nums[k]太大了，k向左移，同时去重
                if(sum > 0){
                    while(j < k && nums[k] == nums[--k]);
                    //如果三数之和小于0，则说明中间数nums[j]太小了，j向右移，同时去重
                }else if(sum < 0){
                    while(j < k && nums[j] == nums[++j]);
                    //如果三数之和等于0, 则把三数添加到答案
                }else{
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[k])));

                    //nums[j]增大, nums[k]减小, 依旧可能满足三数之和为0，继续遍历去重
                    while(j < k && nums[k] == nums[--k]);
                    while(j < k && nums[j] == nums[++j]);
                }
            }

        }
        return res;
    }*/
}
